# 零钱兑换：
# 给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。
# 如果没有任何一种硬币组合能组成总金额，返回 -1。
# 你可以认为每种硬币的数量是无限的。

# 问题：时间过长。



class Solution:
    def coinChange(self, coins: list, amount: int) -> int:

        def dp(n):
            if n == 0: return 0
            if n < 0: return -1
            res = float('INF')
            for coin in coins:
                subProblem = dp(n - coin)
                if subProblem == -1: continue
                res = min(res, 1 + subProblem)

            return res if res != float('INF') else -1

        return dp(amount)


if __name__ == "__main__":
    s=Solution
    a=[1,2,5]
    print(s.coinChange(s,a,100))